# """
# This is the ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
class ArrayReader(object):
    # Compares 4 different elements in the array
    # return 4 if the values of the 4 elements are the same (0 or 1).
    # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
    # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
    def query(self, a: int, b: int, c: int, d: int) -> int:
        pass

    # Returns the length of the array
    def length(self) -> int:
        pass


class Solution:
    def guessMajority(self, reader: 'ArrayReader') -> int:
        size = reader.length()

        # 计算前4个的情况：不妨设第1个为0
        dp = [0]
        v0 = reader.query(1, 2, 3, 4)
        v1 = reader.query(0, 2, 3, 4)
        v2 = reader.query(0, 1, 3, 4)
        v3 = reader.query(0, 1, 2, 4)
        dp.append(0 if v1 == v0 else 1)
        dp.append(0 if v2 == v0 else 1)
        dp.append(0 if v3 == v0 else 1)

        # 计算每一种情况的出现次数
        v0 = reader.query(0, 1, 2, 3)
        for i in range(4, size):
            v1 = reader.query(i - 3, i - 2, i - 1, i)
            if v0 == v1:
                dp.append(dp[-4])
            else:
                dp.append(1 - dp[-4])
            v0 = v1

        n1 = dp.count(0)
        n2 = dp.count(1)
        if n1 > n2:
            return dp.index(0)
        elif n1 < n2:
            return dp.index(1)
        else:
            return -1


if __name__ == "__main__":
    pass
